package leetcode.linked;

import java.util.HashSet;
import java.util.TreeSet;

/**
 * 83. 删除排序链表中的重复元素
 * <p>
 * 给定一个排序链表，删除所有重复的元素，使得每个元素只出现一次。
 * <p>
 * 示例 1:
 * <p>
 * 输入: 1->1->2
 * 输出: 1->2
 * <p>
 * 示例 2:
 * <p>
 * 输入: 1->1->2->3->3
 * 输出: 1->2->3
 * 分析： 需要借助辅助数据结构进行存放数据， 找到当前元素的前一个节点 pre，当前元素节点cur
 * 时间复杂度 因为使用的是HashSet 所以查找元素O(1),总体来说在O(n)级别 空间复杂度O(n) 开辟了一个存放链表的set
 */
public class Solution83 {
    private class ListNode {
        int val;
        ListNode next;

        ListNode(int x) {
            val = x;
        }
    }

    public ListNode deleteDuplicates(ListNode head) {
        HashSet<Integer> set = new HashSet<Integer>();
        //设立虚拟头结点
        ListNode dunmmyHead = new ListNode(-1);
        dunmmyHead.next = head;
        //当前元素的前一个元素
        ListNode pre = dunmmyHead;
        ListNode cur = dunmmyHead.next;
        while (cur != null) {
            if (set.contains(cur.val)) {
                //去重
                ListNode rem = cur;
                pre.next = rem.next;
                cur = pre.next;
                rem.next = null;

            } else {
                //不包含时，放入到set中，移动指针，维持指针含义
                set.add(cur.val);
                pre = cur;
                cur = cur.next;
            }
        }
        return dunmmyHead.next;
    }
}
